package leetcode.Hot100;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Cheng Jun
 * Description: 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * <p>
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * 1 <= heights.length <=105
 * 0 <= heights[i] <= 104
 * @version 1.0
 * @date 2021/12/27 22:16
 * 单调栈+哨兵 的经典题，二刷
 */
public class largestRectangleArea {

    public static void main(String[] args) {
        System.out.println(largestRectangleArea1(new int[]{2, 1, 2}));
    }


    // [2,1,5,6,2,3]
    // 暴力解法
    static public int largestRectangleArea(int[] heights) {
        int max = 0;
        for (int i = 0; i < heights.length; i++) {
            int height = heights[i];
            int width = 1;
            for (int j = i; j < heights.length; j++) {
                height = Math.min(heights[j], height);
                max = Math.max(max, height * width);
                width++;
            }
        }
        return max;
    }

    // 单调栈 + 哨兵
    // https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/
    static public int largestRectangleArea1(int[] heights) {
        int length = heights.length;
        int[] newHeights = new int[length + 2];
        // 相当于加入左右 0 元素
        for (int i = 0; i < heights.length; i++) {
            newHeights[i + 1] = heights[i];
        }
        int maxArea = 0;
        // 单调栈 保存数组下标
        Deque<Integer> stack = new LinkedList<>();
        stack.addLast(0);
        for (int i = 1; i < newHeights.length; i++) {
            while (newHeights[stack.peekLast()] > newHeights[i]) {
                int top = stack.pollLast();
                int curHeight = newHeights[top];
                // 注意宽度的计算，是新的栈顶元素
                // int curWidth = i - top; 错误
                int curWidth = i - stack.peekLast() - 1;
                maxArea = Math.max(maxArea, curHeight * curWidth);
            }
            stack.addLast(i);
        }
        return maxArea;
    }
}
